package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (B卷,200分)- 返回矩阵中非1的元素个数（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 存在一个m*n的二维数组，其成员取值范围为0，1，2。
 * <p>
 * 其中值为1的元素具备同化特性，每经过1S，将上下左右值为0的元素同化为1。
 * <p>
 * 而值为2的元素，免疫同化。
 * <p>
 * 将数组所有成员随机初始化为0或2，再将矩阵的[0, 0]元素修改成1，在经过足够长的时间后求矩阵中有多少个元素是0或2（即0和2数量之和）。
 * <p>
 * 输入描述
 * <p>
 * 输入的前两个数字是矩阵大小。后面是数字矩阵内容。
 * <p>
 * 输出描述
 * <p>
 * 返回矩阵中非1的元素个数。
 * <p>
 * 用例
 * <p>
 * 输入	4 4
 * <p>
 * 0 0 0 0
 * <p>
 * 0 2 2 2
 * <p>
 * 0 2 0 0
 * <p>
 * 0 2 0 0
 * <p>
 * 输出	9
 * <p>
 * 说明
 * 输入数字前两个数字是矩阵大小。后面的数字是矩阵内容。
 * <p>
 * 起始位置(0,0)被修改为1后，最终只能同化矩阵为：
 * <p>
 * 1 1 1 1
 * <p>
 * 1 2 2 2
 * <p>
 * 1 2 0 0
 * <p>
 * 1 2 0 0
 * <p>
 * 所以矩阵中非1的元素个数为9
 * <p>
 * 题目解析
 * <p>
 * 本题可以使用广度优先搜索BFS解决。
 */
public class BFSMatrixOfNon {
    public static void main(String[] args) {
        /*//输入
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();

        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = in.nextInt();
            }
        }*/

        int m = 4;
        int n = 4;
        String input = "0 0 0 0\n0 2 2 2\n0 2 0 0\n0 2 0 0";
        int[][] matrix = Arrays.stream(input.split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(m, n, matrix));
    }

    public static int getResult(int m, int n, int[][] matrix) {
        // 上、下、左、右偏移量
        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 广搜队列
        LinkedList<int[]> queue = new LinkedList<>();

        // 初始时只有矩阵[0,0]位置元素为1
        queue.add(new int[]{0, 0});
        matrix[0][0] = 1;

        // count记录矩阵中值为1的元素的个数
        int count = 1;

        // 广搜
        while (queue.size() > 0) {
            int[] pos = queue.poll();

            int x = pos[0];
            int y = pos[1];

            for (int[] offset : offsets) {
                int newX = x + offset[0];
                int newY = y + offset[1];

                if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
                    matrix[newX][newY] = 1;
                    count++;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }

        return m * n - count;
    }
}